Branch-and-price-and-cut for the Split-collection Vehicle Routing Problem with Time Windows and Linear Weight-related Cost

摘要

This paper addresses a new vehicle routing problem that simultaneouslyinvolves time windows, split collection and linear weight-related cost, whichis a generalization of the split delivery vehicle routing problem with timewindows (SDVRPTW). This problem consists of determining least-cost vehicleroutes to serve a set of customers while respecting the restrictions of vehiclecapacity and time windows. The travel cost per unit distance is a linearfunction of the vehicle weight and the customer demand can be fulfilled bymultiple vehicles. To solve this problem, we propose a exactbranch-and-price-and-cut algorithm, where the pricing subproblem is aresource-constrained elementary least-cost path problem. We first prove that atleast an optimal solution to the pricing subproblem is associated with anextreme collection pattern, and then design a tailored and novel label-settingalgorithm to solve it. Computational results show that our proposed algorithmcan handle both the SDVRPTW and our problem effectively.